package q543_diameterOfBinaryTree;

import CommonClass.Common.TreeNode;

public class Solution {
    int res = 0;
    /*
    直接用dfs解决 dfs返回的是该节点左右最深的层数
    在dfs的过程中更新res即可
    需要注意的是 必须要定义l 和 r 不能直接写在res 和 return 后面的表达式中
    否则超时 如果不用 相当于在算res和return的时候代码算了两遍dfs(root.left), dfs(root.right)
     */
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = dfs(root.left);
        int r = dfs(root.right);
        res = Math.max(l + r, res);

        return Math.max(l, r) + 1;
    }
}
